
%----------------------
%      同余
%----------------------

%\chapter{同余}

\section{同余的基本概念和性质}

\subsection{基本概念}

\begin{definition}{同余(congruence)}
	给定一个正整数m，如果用m去除两个整数a和b所得的余数相同，称a和b模(module)m同余，记为$a\equiv b(mod \space \ m)$。否则，称a和b模m不同余，记为$a\nequiv b(mod \space \ m)$。
\end{definition}
\begin{example}\\
	1(mod 5)=1=6 (mod 5)=11 (mod 5) \\
	2(mod 5)=2=7 (mod 5)=12 (mod 5) \\
	3(mod 5)=3=8 (mod 5)=13 (mod 5) \\
	4(mod 5)=4=9 (mod 5)=14 (mod 5) \\
	5(mod 5)=0=10 (mod 5)=15 (mod 5) 
\end{example}

\subsection{性质}

\begin{theorem}{同余的等价性}{fubi} 
	同余关系是等价关系。	
\end{theorem}

等价是自反、传递、对称，显而易见，自己和自己同余，x和y同余，y也一定和x同余，如果同时y和z同余，那么x和z也同余。

\begin{note}
	当给一个对象贴上一个有明确定义的标签时，其实就是对这个对象有了一个深刻的说明，因为这个标签后面的一切属性此对象都会具有。
\end{note}

\begin{theorem}{同余性质}{fubi}
	\begin{enumerate}[noitemsep]
		\item 数a和b模m同余的充要条件是$m \mid a-b$。
		\item 数a和b模m同余的充要条件是，存在一个整数k使得$a=b+km$。\cite{min2003}
		\item $a+b \equiv c(mod \ m) \Rightarrow a\equiv c-b (mod \ m)$.
		\item $a \equiv b (mod \ m) \Rightarrow gcd(a,m)=gcd(b,m)$.
		\item $a=a_1d,b=b_1d,gcd(d,m)=1,a \equiv b (mod \ m) \Rightarrow a_1 \equiv b_1(mod \ m)$.\cite{min2003}\footnote{公式后面这种标识，表示此公式在整理本书时的出处}
		\item $m,a_1,a_2,b_1,b_2 \in \mathbb{Z},a_1 \equiv b_1 (mod \ m),a_2 \equiv b_2 (mod \ m) \Rightarrow $
			\begin{enumerate}
				\item $a_1x +a_2y \equiv b_1 x +b_2 y (mod \ m),x,y\in \mathbb{Z}$
				\item $a_1a_2 \equiv b_1b_2 (mod \ m)$
				\item $a_1^n \equiv b_1^n (mod \ m),n>0 $
			\end{enumerate}
		\item $f(t)=a_n t^n +a_{n-1}t^{n-1}+ \ldots + a_1 t +a_0,g(t)=b_n t^n +b_{n-1}t^{n-1}+ \ldots + b_1 t +b_0$是两个整系数多项式，且$a_i \equiv b_i (mond \ m),$若$x \equiv y (mod \ m)$,则$f(x) \equiv g(y)(mod \ m)$.
	\end{enumerate} 	
\end{theorem}

我们可以设$a=k_1 m + r_1,b=k_2 m +r_2$,然后去讨论证明以上定理。\par
设m=5，11和1同余吗？由于$11-1=10$,10可以整除5，由上面的定理可知，11和1模5同余。或者说，由于$11=1+2 \times 5$，所以11和1模5同余。\par
那么3879和3657模5同余吗？$3879-3657=222,5 \nmid 222$，所以3879和3657不同余。

前面的同余性质都是在模不变的情况下进行讨论，下面我们看看另外一些同余的性质，这些性质是模在变化的时候所保持的。\par

\begin{theorem}{}{int}
	\begin{itemize}
		\item  $ac \equiv bc (mod \ m),gcd(c,m)=d \Rightarrow a \equiv b (mod \ \frac{m}{d})$.\label{thm:samedivide}
		\item $a \equiv b (mod \ m) \Rightarrow ak \equiv bk (mod \ mk),k \in \mathbb{Z}$.
		\item $a \equiv b (mod \ m),d \mid m,d \in \mathbb{Z} \Rightarrow a \equiv b (mod \ d)$.
		\item $a \equiv b (mod \ m_i),i=1,2,\ldots,n \Rightarrow a \equiv b (mod \ lcm(m_1,m_2,\ldots,m_n)) $
	\end{itemize}
\end{theorem}
\begin{example}
	$m=9,5 \times 3 \equiv 2 \times 3(mod \ 9),gcd(3,9)=3$,根据定理~\ref{thm:samedivide},$5 \equiv 2 (mod\ \frac{9}{3}) \Rightarrow 5 \equiv 2 (mod\ 3)$\\
	$m=9,5 \times 6 \equiv 2 \times 6(mod \ 9),gcd(6,9)=3$,根据定理~\ref{thm:samedivide},$5 \equiv 2 (mod\ \frac{9}{3}) \Rightarrow 5 \equiv 2 (mod \ 3)$
\end{example}

\section{剩余系(residue system)}
同余为整数集合上的等价关系，所以可以利用同余关系吧整数集合$\mathbb{Z}$划分为若干等价类。
\begin{theorem}{\cite{min2003}}{fubi}
	m是一个给定的正整数，则全部整数可分成m个集合，记作$C_0,C_1,\ldots,C_{m-1}$,其中$C_r(r=0,1,\ldots,m-1)$是由一切形如$qm+r(q=0,\pm 1,\pm 2,\ldots)$的整数所组成，这些集合具有下列性质：\\
	(1)每一个整数必包含在且仅在上述的一个集合里。\\
	(2)两个整数在一个集合中的充要条件是这两个整数对模m同余。
\end{theorem}

\begin{definition}{剩余类(residue class)}{int}
	m是一个给定的正整数，$C_r$表示所有与整数r模m同余的整数组成的集合，$C_r$叫做模m的一个剩余类，一个剩余类中的任一元素叫做该类的代表元。
\end{definition}

\begin{example}\\
	1 (mod 5)=11 (mod 5),11(mod 5)= 16 (mod 5) $\Rightarrow$ 1 (mod 5)=16 (mod 5) \par

	模5，r=1,$C_1 =\left\lbrace 1,6,11,16,21,\ldots\right\rbrace ;r=2,C_2 = \left\lbrace 2,7,12,17,22,\ldots \right\rbrace ; r=3, C_3 = \left\lbrace 3,8,13,18,23,\ldots \right\rbrace $ 
\end{example}

\begin{definition}{完全剩余系(complete system of residues)}{int}
	在模m的剩余类$C_0,C_1,C_2,\ldots,C_{m-1}$中各取一代表元$a_i \in C_i,i=0,1,\ldots,m-1,$则此m个数称为模m的一个完全剩余系（又称完系）。
\end{definition}

\begin{example}\\
	\begin{quote}
		模5的三个完全剩余系：\\
		0,1,2,3,4\\
		1,2,3,4,5\\
		2,3,4,5,6\\
		\ldots 
	\end{quote}
\end{example}

\begin{definition}{特殊剩余系定义}{int}
	对于正整数m\\
	(1)  $0,1,\ldots,m-1$为模m的一个完全剩余系，并且叫做模m的最小非负完全剩余系。\\
	(2)  $1,2,\ldots,m-1,m$为模m的一个完全剩余系，并且叫做模m的最小正完全剩余系。\\
	(3)  $-(m-1),\ldots,-1,0$为模m的一个完全剩余系，并且叫做模m的最大非正完全剩余系。\\
	(4)  $-m,-(m-1),\ldots,-1$为模m的一个完全剩余系，并且叫做模m的最大负完全剩余系。
\end{definition}

\begin{example}\\
	\begin{quote}
		模m=5,\\
		0,1,2,3,4是模5的最小非负完全剩余系。\\
		1,2,3,4,5是模5的最小正完全剩余系。\\
		0,-1,-2,-3,-4是模5的最大非正完全剩余系。\\
		-1,-2,-3,-4,-5是模5的最大负完全剩余系。\\
	\end{quote}
\end{example}
\begin{theorem}{\cite{min2003}}{fubi}
	m是正整数，gcd(a,m)=1,b是任意整数，若x遍历模m的一个完全剩余系，则ax+b也遍历模m的完全剩余系。
\end{theorem}
\begin{theorem}{\cite{min2003}}{fubi}
	$m_1,m_2$是两个互质的正整数，$x_1,x_2$分别遍历模$m_1,m_2$的完全剩余系，则$m_2x_1+m_1x_2$也遍历模$m_1 \times m_2$的完全剩余系。
\end{theorem}

\section{欧拉定理}
\subsection{基本概念}
\begin{definition}{剩余类与m互素}{int}
	在模m的一个剩余类中，若有一个数与m互素，则该剩余类中所有数都与m互素，此时称该剩余类与m互素。
\end{definition}

\begin{example}
	$m=26,C_5 = {5,31,57,\ldots},gcd(5,26)=1,gcd(31,26)=1,\ldots$
\end{example}

\begin{example}
	$m=6,C_5 = {5,11,17,\ldots},gcd(5,6)=1,gcd(11,6)=1,\ldots$\\
\end{example}

\begin{definition}{欧拉函数(Euler's totient function或称totient function)}{int}
	设m是正整数，在m的所有剩余类中，与m互素的剩余类的个数称为m的欧拉函数，记为$\varphi (m)$。
\end{definition}
我们也可以将欧拉函数定义为，集合$\{ 0,1,\ldots,m-1 \} $中与m互素的整数个数。\par
\begin{example}\\
	$\varphi (6)=2$，这是因为$\{ 0,1,2,3,4,5 \} $中与6互素的只有1，5。\\
	$\varphi (12)=4$,这是因为$\{ 0,1,2,3,4,5,6,7,8,9,10,11 \} $中与12互素的只有1，5,7,11。\\
	$\varphi (1)=1$\\
	如果p为素数，$\varphi (p)=p-1$
\end{example}

\subsection{欧拉函数的计算}
求解欧拉函数，我们可以用定义来求解，这需要我们遍历一个完全剩余系，并且判断和其互素的数，运算量还是挺大的。\par
下面看一种利用整数标准分解式求解欧拉函数的方法。

\begin{theorem}{欧拉函数求解定理}{fubi}
	设m有标准分解式$m=p_1^{a_1}p_2^{a_2} \ldots p_s^{a_s},a_i>0,i=1,2,\ldots,s$，则$\varphi(m)=m\prod\limits^{s}_{i=1}(1-\frac{1}{p_i})$
\end{theorem}

\begin{example}
	$360=2^2 \times 3^2 \times 5,\varphi(360)=360(1-\frac{1}{2})(1-\frac{1}{3})(1-\frac{1}{5})=2^2 \times 3^2 \times 5 \times (1-\frac{1}{2})(1-\frac{1}{3})(1-\frac{1}{5})=(2^3-2^2)(3^2-3)(5-5^0)=4 \times 6 \times 4 = 96$
\end{example}

\begin{theorem}{\cite{min2003}}{fubi}
	若$m_1,m_2$是互质正整数，则，$\varphi(m_1m_2)=\varphi(m_1)\varphi(m_2)$.
\end{theorem}

\subsection{简化剩余系}

\begin{definition}{缩剩余系/简化剩余系(reduced residue system)}{int}
	设m是正整数，在与模m互素的$\varphi(m)$个剩余类中，各取一个代表元组成一个集合，此集合叫做模m的缩剩余系(有时简称缩系)或者简化剩余系。
\end{definition}

简化剩余系中元素的个数为$\varphi(m)$.
\begin{example}\\
	\{1,5\}是m=6的一个缩系；\\
	\{1，2，3，4，5，6\}是m=7的一个缩系；\\
	\{1,5,7,11\}是m=12的一个缩系。
\end{example}

利用以下定理可以构造简化剩余系。
\begin{theorem}{简化剩余系构造定理}{fubi}
	设m是正整数，整数a满足gcd(a,m)=1。若x遍历模m的一个简化剩余系，则ax也遍历模m的一个简化剩余系。
\end{theorem}

\begin{example}\\
	整数5与6互素，a=5，m=6，x遍历\{1,5\}，ax遍历\{5,25\}，\{5,25\}是m=6的一个缩系；\\
	整数3与7互素，a=3，m=7，x遍历\{1，2，3，4，5，6\}，ax遍历\{3，6，9，12，15，18\}，\{3，6，9，12，15，18\}是m=7的一个缩系；\\
	整数5与12互素，a=5，m=12，x遍历\{1,5,7,11\}，x遍历\{5,25,35,55\}，\{5,25,35,55\}是m=12的一个缩系。
\end{example}

\begin{theorem}{\cite{min2003}}{fubi}
	$gcd(m_1,m_2)=1$,$x_1,x_2$分别遍历$m_1,m_2$的简化剩余系，则$m_2x_1+m_1x_2$遍历模$m1\times m_2$的简化剩余系。
\end{theorem}

\subsection{欧拉定理}
\begin{theorem}{欧拉定理(Euler Theorem)}{fubi}
	
	设m是大于1的整数，若a是满足$gcd(a,m)=1$的整数，则$a^{\varphi(m)} \equiv 1 \left( mod \ m \right) $。
	
\end{theorem}

\begin{example}\\
	$\varphi (6)=2,gcd(5,6)=1$，计算$a^{\varphi(6)} =5^2=25 \equiv 1 (mod 6)$。\\
	$\varphi (12)=4,gcd(5,12)=1$，计算$a^{\varphi(12)} =5^4=625 \equiv 1 (mod 6)$。\\
\end{example}

\section{乘法逆元}
本节研究模正整数的乘法运算的可逆性问题，先看一个例子。\par
模10的最小非负完全剩余系\{ 0,1,2,3,4,5,6,7,8,9\} 中，在模10的运算下有：\\
\begin{center}
	$1\times 1 \equiv 1 (mod 10)$\\
	$3\times 7 \equiv 1 (mod 10)$\\
	$9\times 9 \equiv 1 (mod 10)$\\
\end{center}
也就是说当$a \in \left\lbrace 1,3,7,9 \right\rbrace  $时，存在$a' \in \left\lbrace  0,1,2,3,4,5,6,7,8,9\right\rbrace $,使得$aa' \equiv 1 (mod \  10)$,而对于\{ 0,2,4,5,6,8\}集合中的数，不具有这样的性质，而集合 \{1,3,7,9\}恰好是10的简化剩余系。
\subsection{逆元(inverse)定义}
\begin{theorem}{逆元存在性}{fubi}
	若a是满足$gcd(a,m)=1$的整数，则存在唯一的整数$a',1 \leq a' < m$ ,且$gcd(a',m)=1$,使得$aa'\equiv (mod \ m)$。
\end{theorem}

\begin{example}\\
	\{1,5\}是m=6的一个简化剩余系系；$1 \times 1 \equiv 1 (mod \ 6),5 \times 5 \equiv 1 (mod \ 6)$\\
	\{1，2，3，4，5，6\}是m=7的一个简化剩余系；$1 \times 1 \equiv 1 (mod \ 7),2 \times 4 \equiv 1 (mod \ 7),3 \times 5 \equiv 1 (mod \ 7),4 \times 2 \equiv 1 (mod \ 7),5 \times 3 \equiv 1 (mod \ 7),6 \times 6 \equiv 1 (mod \ 7)$\\
	\{1,5,7,11\}是m=12的一个简化剩余系;$1 \times 1 \equiv 1 (mod \ 12),5 \times 5 \equiv 1 (mod \ 12),7 \times 5 \equiv 1 (mod \ 12),7 \times 5 \equiv 1 (mod \ 12), 11 \times 1 \equiv 1 (mod \ 12)$。
\end{example}

\begin{definition}{乘法逆元(multiplicative inverse)}{fubi}
	对于正整数m和整数a，满足$gcd(a,m)=1$，存在唯一一个m的剩余类，其中对于每一个元素a'，都会使$aa' \equiv 1(mod \ m)$成立，此时称a'为a模m的乘法逆元，记作$a'(mod \ m)$或$a^{-1}(mod\ m)$。
\end{definition}

\subsection{逆元求解}
逆元的求解在公钥密码学中非常重要，但是当m和a比较大时，直接利用定义很难求解，所以如何快速求解逆元，是一个重要的研究内容。扩展欧几里得算法就是一种快速求解逆元的算法。\par
\begin{theorem}{贝祖定理(Bézout's identity)}{fubi}
	任何整数a、b,一定存在整数x,y，使$ax+by=gcd(a,b)$成立。
\end{theorem}
欧几里得算法的数学基础是$a = bq+r \Rightarrow gcd(a,b)=gcd(b,r),r=a-[\frac{a}{b}]b$,根据贝祖定理，我们有，$gcd(a,b)=ax_1+by_1,gcd(b,r) = bx_2+(a-[\frac{a}{b}]b)y_2$,对于第二个式子我们进行重新整理，$bx_2+(a-[\frac{a}{b}]b)y_2 = bx_2 + ay_2-[\frac{a}{b}]by_2 = ay_2 +b(x_2-[\frac{a}{b}]y_2)$,由于$gcd(a,b)=gcd(b,r)$，所以有$ax_1+by_1 = ay_2 +b(x_2-[\frac{a}{b}]y_2) \Rightarrow x_1=y_2,y_1=x_2-[\frac{a}{b}]y_2$，一直计算下去，就可以得出扩展欧几里得算法。
\begin{theorem}{扩展欧几里得算法}(extend Euclid's Algorithm){fubi}
	设$r_0,r_1$是两个正整数，且$r_0 > r_1$，设$r_i (i=1,2,\ldots,n)$是使用欧几里得算法计算$gcd(r_0,r_1)$时所得到的余数序列且$r_{n+1} =0$，则可以使用如下算法求整数$s_n$和$t_n$，使得$gcd(r_0,r_1)=s_n r_0 + t_n r_1$。$s_n,t_n$是如下递归定义的序列的第n项。\\
	$s_0=1,t_0 =0$\\
	$s_1=0,t_1 =1$\\
	$s_i=s_{i-2} - q_{i-1} s_{i-1},t_i =t_{i-2}-q_{i-1} t_{i-1}$，其中$q_i = r_{i-1} / r_i,i=2,3,\ldots,n.$\\
\end{theorem}
扩展欧几里得算法是在计算贝祖(Bézout,也有翻译为“裴蜀”的)等式$ax+bx=gcd(a,b)$的整数解，而贝祖等式是a，b和它们的最大公约数d之间的线性丢番图方程。当$gcd(r_0,r_1)=1$时，有$s_n r_0 + t_n r_1 =1$,等式两边同取模，等式不变，所以有$s_n r_0 + t_n r_1 \equiv s_n r_0 (mod \ r_1)$,由逆元定义知$r_0^{-1}=s_n (mod \ r_1)$,同理，可以知道$r_1$的逆元， $r_1^{-1}=t_n (mod \ r_0).$\par

\begin{example}\\
	a=529,m=130，求a模m的乘法逆元。
\end{example}
\begin{solution}
	由前面最大公约数的计算（见下），可知a和m互素。\\
	$
	529=130 \times 4 + 9 \newline
	130=9 \times 14 +4 \newline
	9=4 \times 2 +1  \\
	4=1 \times 4 +0  \\
	gcd(529,130)=1
	$\\
	下面我们求解模130时，529的逆元，或者模529，130的逆元。\\
		
	为了使得过程更加清晰，我们做一张表，展示其过程：\\
	\begin{tabular}{|c|c|c|c|c|}
		\hline 
		i & $r_i$ & $q_i$ & $s_i=s_{i-2} - q_{i-1} s_{i-1}$ & $t_i=t_{i-2}-q_{i-1} t_{i-1}$\\ 
		\hline 
		0 & 529 & - & $s_0=1$ & $t_0=0$ \\ 
		\hline 
		1 & 130 & 4 & $s_1=0$ & $t_1=1$ \\ 
		\hline 
		2 & 9 & 14 & $s_2=s_0-q_1 s_1=1-4 \times 0=1$ & $t_2=t_0-q_1t_1=0-4 \times 1=-4$\\ 
		\hline 
		3 & 4 & 2 & $s_3=s_1-q_2 s_2=0-14 \times 1=-14$ & $t_3=t_1-q_2t_2=1-14 \times (-4)=57$\\ 
		\hline
		4 & 1 & 4 & $s_4=s_2-q_3 s_3=1-2 \times (-14)=29$ & $t_4=t_2-q_3t_3=-4-2 \times 57=-118$\\ 
		\hline
		5 & 0 & - & - & -\\ 
		\hline
	\end{tabular} 
	$529 \times 29 \equiv 1 (mod \ 130)$\\
	$130 \times (-118) \equiv -528 \equiv 1 (mod \ 529)$.
\end{solution}

\section{费马小定理}
\begin{theorem}{费马小定理(Fermat's little theorem,1963)}{fubi}
	p是素数,a为任意整数,则$a^p \equiv a (mod \ p)$。\cite{jia2017}
\end{theorem}
上面的定理也有写作,若p是素数，则对任意整数a，如果a和p互素，有$a^{p-1} \equiv 1 (mod \ p)$。 这种写法要求a和p互素\par
费马小定理是欧拉定理的一种特殊情况。\par
\begin{example}\\
	3是素数，$2^3=8 \equiv 2 (mod 3)$,$4^3=64 \equiv 1 \equiv 4(mod\ 3)$,$6^3=216 \equiv 0 \equiv 6(mod 3)$;\\
	7是素数，$2^7=128 \equiv 2 (mod 7)$,$4^7=16384 \equiv 4 (mod 7)$,$6^7=279936 \equiv 6 (mod 7)$;\\
\end{example}

可以用费马小定理来求逆元呢.\par
由费马小定理 $a^{p-1} \equiv 1$ , 变形得 $a a^{p-2}\equiv 1(mod \ p)$，很明显了,若a,p互质,因为$a a^{p-2}\equiv 1(mod \ p)$,则$a^{-1}=a^{p-2}(mod \ p)$,用快速幂可快速求之。

\section{威尔逊定理}
威尔逊定理、欧拉定理、孙子定理（中国剩余定理）、费马小定理并称数论四大定理。下面我们看看威尔逊定理。
\begin{theorem}{威尔逊定理(Wilson’s theorem)}{fubi}
	p是一个素数$\Leftrightarrow (p-1)! \equiv -1(mod \ p).$
\end{theorem}
威尔逊定理给出了素数的充要条件，那么我们可以用p-1的阶乘来判断p是否为素数，但由于阶乘的计算量太大，通常不会使用。
\begin{example}\\
	$(3-1)!=2 \equiv 2 (mod 3) \equiv -1 (mod 3)$;\\
	$(5-1)!=24 \equiv 4 (mod 5) \equiv -1 (mod 5)$;\\
	$(7-1)!=720 \equiv 6 (mod 7) \equiv -1 (mod 7)$;\\
	$(11-1)!=3628800 \equiv 10 (mod 11) \equiv -1 (mod 11)$;\\
\end{example}

\section{RSA 12位密码系统示例}
RSA加密算法是一种非对称加密算法。在公开密钥加密和电子商业中RSA被广泛使用。RSA是1977年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的，后来这三个人创立了有名的安全公司RSA(网站www.rsa.com)。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。对极大整数做因数分解的难度决定了RSA算法的可靠性。到目前为止，世界上还没有任何可靠的攻击RSA算法的方式。只要其钥匙的长度足够长，用RSA加密的信息实际上是不能被解破的。\footnote{本段内容摘自https://baike.baidu.com/item/RSA算法/263310?fr=aladdin ，可以从网页上获得更多的介绍信息，并且此条信息由百度的“科普中国科学百科词条编写与应用工作项目"审核}\par
下面以12位演算RSA的加密解密与暴力破方法，讲解RSA的基本原理\footnote{此节采用的例子素材来源于https://www.jianshu.com/p/4e302869d057}。\par
\subsection{加密系统}
(1) 生成公私钥对\par
RSA是非对称加密，有公钥和私钥，公钥公开给加密方加密，私钥留给自己解密，是不公开的。\par
1.随机选两个素数，用p、q来代替 （素数的数值越大，位数就越多，可靠性就越高。假设我们取p = 47，q = 59。\par
\begin{note}
	如何实现一个算法实现随机选两个素数？
\end{note}
2.计算这两个素数的乘积，$n =p \times q = 47 \times 59 = 2773$,n的长度就是公钥长度。2773写成二进制是101011010101，一共有12位，所以这个密钥就是12位。实际应用中，RSA密钥一般是1024位，重要场合则为2048位。\par
\begin{note}
	在实际的RSA系统中，比如密钥是1024位，也就是意味着要在限定一个数的位数情况下，如何选取两个素数，乘积满足这样的要求。
\end{note}
3.计算n的欧拉函数$\phi(n)$,$\phi(n) = (p-1)(q-1) $,$\phi(2773) = (47 - 1) \times (59 - 1) = 46 \times 58 = 2668$.\par
4.随机选择一个整数e，$1< e < \phi(n)$，且e与$\phi(n)$ 互素（我们知道，此时$e^{\phi(n)} \equiv 1 (mod  n)$）.例如我们在1到2668之间，随机选择了17，e = 17。\par
5.计算e对于$\phi(n)$的模乘法逆元d，当$gcd(e,\phi(n)) =1$，$ed \equiv 1 (mod \ \phi(n)) \Rightarrow d = (1+k\phi(n)) / e,k \in \mathbb{Z}$,代入各值，$d=(1+2668k)/17$,可以依次给k赋值，取d为整数的序偶，得到一系列(k,d),(1,157)、(18,2825)、(35,5493) $\ldots$,随机选一个序偶，比如(1,157)，也就是d=157.\par
6.将n和e封装成公钥，n和d封装成私钥，即公钥为：n = 2773，e = 17，私钥为：n = 2773，d = 157。\par
(2) 用公钥加密字符串\par
假设我们加密一个字符"A"，首先字符要用数值表示（）这就是编码，信源编码），一般用Unicode或ASCII码表示，此处我们用ASCII码表示，
"A"的ASCII码十进制为65(十六进制0x41)，我们用m来代替明文(message)，c来代替密文(cipher)，m = 65，RSA加密公式：$m^e \equiv c (mod n)$,代入各值$65^{17} (mod \ 2773) \equiv 6,599,743,590,836,592,050,933,837,890,625 (mod \ 2773) \equiv 332 (mod \ 2773),c=332$\par
(3) 用私钥解密密文\par
RSA解密公式：$c^d \equiv m (mod \ n)$,代入各值，$c^d \equiv 332^{157} \equiv 6.5868707484014117339891253968203e+395 \equiv 65  (mod \ 2773),m=65$.

\subsection{暴力破解}
RSA的可靠性在于因数分解的难度，因为p、q、n、$\phi(n)$、e、d这六个数字之中，公钥用到了两个n和e，其余四个数字都是不公开的。其中最关键的是d，因为n和d组成了私钥，一旦d泄漏，就等于私钥泄漏.\par
(1) $ed \equiv 1 (mod \ \phi(n))$。只有知道e和$\phi(n)$，才能算出d。\par
(2) $\phi(n)=(p-1)(q-1)$。只有知道p和q，才能算出$\phi(n)$。\par
(3) $n=pq$。只有将n因数分解，才能算出p和q。\par
由此可见推导出d就必须因数分解出p和q,公钥里面有n = 2773,那么暴力破解的方法就是把2773因数分解出两个相乘的素数。可以编程对此例进行暴力破解。

\section{线性同余方程}

\subsection{基本概念}

\begin{definition}{同余方程}{def}
	多项式
	$f (x) = a_n x^n + a_{n-1} x^{n-1} + \ldots +a_1 x + a_0 ,n>0,a_i \ (i=0,1,\ldots,n)$
	是整数，设$m > 0$，则同余式$f(x) \equiv 0(mod \ m)$称为模m的同余方程，若$a_n$不能被m整除，则n称为$f(x)$的次数，记为$deg \ f(x)$。若$x_0$满足$f(x_0) \equiv 0 (mod \ m),$则$x \equiv x_0(mod \ m)$叫做此同余方程的解。不同的解是指互不同余的解。
\end{definition}

\subsection{求解方法}
求解同余方程，最直观的方法是采用遍历所有取值的方法。
\begin{example}\\
	求$x^4 + 3x^2-2x+1 \equiv 0 (mod \ 5)$
\end{example}
\begin{solution}
	$x=0,0+0-0+1=1 \equiv 1 (mod \ 5)$\\
	$x=1,1+3 \times 1-2\times 1+1=3 \equiv 3 (mod \ 5)$\\
	$x=2,16+12-4+1=25 \equiv 0 (mod \ 5)$\\
	$x=3,729+27-6+1=751 \equiv 1 (mod \ 5)$\\
	$x=4,256+48-8+1=297 \equiv 2 (mod \ 5)$\\
\end{solution}
\begin{note}
	是不是遍历一个完全剩余系，就算遍历了？我们以上面为例，先看模5的$C_2={2,7,12,17,\ldots}$,x=7带入$x^4 + 3x^2-2x+1$有，$7^4 + 3 \times 7^2-2\times 7+1=2535 \equiv 0 (mod \ 5) $,x=12带入，有$12^4 + 3 \times 12^2-2\times 12+1=21145 \equiv 0 (mod \ 5) $，再看$C_0={0,5,10,15,20,\ldots}$,x=5带入，有$5^4 + 3 \times 5^2-2\times 5+1=690 \equiv 1 (mod \ 5) $，x=10带入，有$10^4 + 3 \times 10^2-2\times 10+1=10281 \equiv 1 (mod \ 5) $.\par
	
	如何想证明，我们就要看各个运算是否同余相等，比如$a \equiv b (mod \ m),c \in \mathbb{Z} \Rightarrow a+c \equiv b+c (mod \ m)$.
\end{note}

\begin{example}\\
	求$x^2 +1 \equiv 0 (mod 7)$
\end{example}
\begin{solution}
	遍历后无解。
\end{solution}

\subsection{线性(or一次)同余方程}
\begin{theorem}{}{fubi}
	设$m>1,gcd(a,m)=1$,同余方程$ax \equiv b(mod \ m)$有且仅有一个解$x_0,x_0 \equiv ba^{\varphi (m)-1}(mod \  m)$.
\end{theorem}
\begin{proof}
	$1,2,\ldots,m$组成模m的一个完全剩余系，因为gcd(a,m)=1，故$a,2a,\ldots,ma$也组成一个模m的完全剩余系，那么有且只有一个数aj，满足$aj=b(mod\ m)$，所以x=j是上式的唯一解。\par
	因为gcd(a,m)=1，由欧拉定理，有$a^\phi(m) \equiv 1(mod\ m)$,根据同余的性质，我们有$a^\phi(m)b \equiv b(mod\ m) \Rightarrow aa^\phi(m-1)b \equiv b(mod\ m) \Rightarrow x=a^\phi(m-1)b$是上式同余方程唯一解。
\end{proof}

\begin{example}\\
	求$5x \equiv 3 (mod 6)$的解。
\end{example}
\begin{solution}\\
	已知$gcd(5,6)=1,\varphi(6)=2$，由以上定理知其有且只有一个解$x \equiv 3\cdot5 \equiv 15 (mod 6) \equiv 3 (mod 6)$.
\end{solution}

\begin{theorem}{\cite{jia2017}}{fubi}
	设$m>1,gcd(a,m)=d>1$,同余方程$ax \equiv b(mod \ m)$有解的充要条件是$d \mid b$，并且在此同余方程有解时，其解的个数是d，若$x\equiv x_0 (mod \ m)$是此方程的特解，则它的d个解为$x \equiv x_0 + \frac{m}{d}t \ (mod \ m) \ t=0,1, \ldots,d-1$。
\end{theorem}

\begin{example}\\
	求解$28x \equiv 21 (mod 35)$
\end{example}
\begin{solution}
	$gcd(28,35)=7$，且$7 \mid 21$,故此方程有解。\\
	$4x \equiv 3 (mod 5)$,$x_0=2$是一个特解。\\
	$x \equiv 2+ \frac{35}{7}t,t=0,1,2,\ldots,6$,可求得解为2，7，12，17，22，17，32.
\end{solution}

\section{同余方程组的求解}
\subsection{中国剩余定理}
我国古代的一部数学著作《孙子算经》中，有一类叫做“物不知数”的问题，原文为：今有物不知其数（四声），三三数（三声）之剩二，五五数之剩三，七七数之剩二，问物几何？\\
这个问题就是求解同余方程组：\par
\begin{center}
$
	\begin{cases}
	x \equiv 2 (mod \ 3)\\
	x \equiv 3 (mod \ 5)\\
	x \equiv 2 (mod \ 7)\\
	\end{cases}
$
\end{center}

我国明代数学家程大位在《算法统宗》这部著作中，把此题解法用一首优美的诗来总结：\\
\begin{center}
	三人同行七十稀，五树梅花廿一枝，\\
	七子团圆整半月，除百零五便得知。\\
\end{center}
这首诗翻译为现代汉语的意识就是，此未知数除3所得余数乘70，除5所得余数乘21，除7所得余数乘15，然后相加除105便是此未知数的取值。用算式表示为：\\
\centerline{$( 2 \times 7 + 3 \times 21 + 2 \times 15 ) \equiv 23 (mod \ 105) $ \\}
计算知此数为23。\par
由上计算方法可见，2，3，2为余，7，21，15分别为模7，模3$\times$模7，模3$\times$模5，是否有规律可循，对于此思路的详细阐述，见\cite{jia2017} 中相应部分的描述(第71页)。


\begin{theorem}{中国剩余定理(chinese remainder theorem,CRT)\cite{jia2017}}{fubi}
	设$m_1,m_2,\ldots,m_k$是k个两两互素的正整数，若令$m=m_1 m_2\ldots m_k, M_i = m_1m_2\ldots m_{i-1} m_{i+1}\ldots m_k,m=m_i M_i$,则对于任意的整数$b_1,b_2,\ldots,b_k$,同余方程组\\
	\begin{center}
	$
	\begin{cases}
		x \equiv b_1 (mod\ m_1)\\
		x \equiv b_1 (mod\ m_1)\\
		\ldots \\
		x \equiv b_k (mod\ m_k)\\
	\end{cases}
	$
	\end{center}
	有唯一解$x \equiv M'_1 M_1 b_1 + M'_2 M_2 b_2 +\ldots + M'_k M_k b_k (mod\ m)$,其中$M'_i$为$M_i$的逆元，$M'_i M_i \equiv 1 (mod\ m_i),i=1,2,\ldots,k$ 。
\end{theorem}

\begin{example}\\
	韩信点兵，有兵一队，若列五行纵队，末行一人，列六行纵队，末列五人，列七行纵队，末行四人，列十一行纵队，末行十人，求兵数。
\end{example}
\begin{solution}
	转化为同余方程组：\\
	\begin{center}
		$
		\begin{cases}
		x \equiv 1 (mod\ 5)\\
		x \equiv 5 (mod\ 6)\\
		x \equiv 4 (mod\ 7)\\
		x \equiv 10 (mod\ 11)\\
		\end{cases}
		$
	\end{center}
	应用CRT,$m=5 \times 6\times 7 \times 11 = 2310$。\\
	$M_1 =2310 / 5 = 462,M^{-1}_1 \equiv 3 (mod\ 5)$\\
	$M_2 =2310 / 6 = 385,M^{-1}_2 \equiv 1 (mod\ 6)$\\
	$M_3 =2310 / 7 = 330,M^{-1}_3 \equiv 1 (mod\ 7)$\\
	$M_4 =2310 / 11 = 210,M^{-1}_4 \equiv 1 (mod\ 11)$\\
	$x \equiv 462 \cdot 3 \cdot 1 + 385 \cdot 1 \cdot 5 + 330 \cdot 1 \cdot 4 +210 \cdot 1 \cdot 10$ $\equiv$ 6731 $\equiv 2111 (mod\ 2310)$
\end{solution}
\subsection{一般一次同余方程组的解}
在中国剩余定理中，要求$m_1,m_2,\ldots,m_k$两两互素，如果不互素，如何求解同余方程组的解？我们看下面的定理。

\begin{theorem}{}{fubi}
	同余方程组
	$\begin{cases}
		x \equiv b_1(mod \ m_1)\\
		x \equiv b_2(mod \ m_2)\\
	\end{cases}$
	有解的充要条件是$gcd(m_1,m_2) \mid (b_1-b_2)$.如果这个条件成立，则此同余方程组模$lcm(m_1,m_2)$有唯一解。\cite{jia2017}
\end{theorem}
对于一次同余方程组\\
\begin{center}
	$
	\begin{cases}
	x \equiv b_1 (mod\ m_1)\\
	x \equiv b_1 (mod\ m_1)\\
	\ldots \\
	x \equiv b_k (mod\ m_k)\\
	\end{cases}
	$
\end{center}
$k \geq 3$,若$gcd(m_1,m_2) \mid (b_1-b_2)$，可先求得前两个方程解$x \equiv b'_2(mod \ lcm(m_1,m_2))$.若$gcd(lcm(m_1,m_2),m_3) \mid (b'_2,b_3)$,则$x \equiv b'_2(mod \ lcm(m_1,m_2))$与$x\equiv b_3(mod \ m_3)$进行联立求解，以此类推，可以求得最后的解。

\begin{example}{\cite{jia2017}}
	判断以下方程是否有解\\
	\begin{center}
		$
		\begin{cases}
		x \equiv 11 (mod\ 36)\\
		x \equiv 7 (mod\ 40)\\
		x \equiv 32 (mod\ 75)\\
		\end{cases}
		$
	\end{center}
\end{example}
\begin{solution}
	$gcd(36,40)=4,gcd(36,75)=3,gcd(40,75)=5$\\
	$b_1-b_2=11-7=4,b_1-b_3=11-32=-21,b_2-b_3=7-32=-25$\\
	因为$4 \mid4,3 \mid -21,5 \mid -25$,所以此方程组一定有解,且解的模数为$lcm(36,40,75)=1800$。\\
	依次联立解方程组，最后可得$x \equiv 407(mod \ 1800)$.
\end{solution}

\section{高次同余方程的解}
本节只是初步讨论一下高次同余方程的解的情况。
\begin{theorem}{\cite{min2003}\footnotemark}{highorcon}\label{thm:highorcon}%需要引用加label，同时注意名字的形式为 thm:*%
	若$m_1,m_2,\ldots,m_k$是k个两两互质的正整数，$m=m_1m_2\ldots m_k$，则同余方程$f(x)\equiv 0(mod\ m)$与同余方程组$f(x) \equiv 0(mod\ m_i),i=1,2,\ldots,k$等价。用$T_i$表示方程$f(x) \equiv 0(mod\ m_i),i \in \{1,2,\ldots,k\}$的解数,T表示$f(x)\equiv 0(mod\ m)$的解数，则有$T=T_1\times T_2 \times \ldots \times T_k$.
\end{theorem}
\footnotetext{为了便于初学者理解，在闵嗣鹤先生的《初等数论》一书中此定理的描述上做了一点修改}
\begin{example}
	求解同余式$x^4 + 2x^3 + 8x +9 \equiv 0 (mod\ 35)$.\cite{min2003}
\end{example}
\begin{solution}\par
	$35=5 \times 7$，且$gcd(5,7)=1$,由此可知题中方程与以下方程组等价：\\
	\begin{center}
		$\begin{cases}
		x^4 + 2x^3 + 8x +9 \equiv 0 (mod\ 5)\\
		x^4 + 2x^3 + 8x +9 \equiv 0 (mod\ 7)\\
		\end{cases}$
	\end{center}
	
	采用遍历的方法可知方程组中第一个方程有两个解$x \equiv 1,4 (mod\ 5)$，第二个方程有三个解$x \equiv 3,5,6 (mod\ 7)$，根据上述定理，题中同余方程解有$2 \times 3=6$个解。\par
	下面我们看看如何求出题中方程的解。\par
	方程等价于以下方程组：\par
	\begin{center}
		$
		\begin{cases}
		x \equiv 1 (mod\ 5)\\
		x \equiv 4 (mod\ 5)\\
		x \equiv 3 (mod\ 7)\\
		x \equiv 5 (mod\ 7)\\
		x \equiv 6 (mod\ 7)\\
		\end{cases}
		$
	\end{center}
	\par
	我们有$7 \times 3 \equiv 1 (mod\ 5),5 \times 3 \equiv 1(mod\ 7)$利用中国剩余定理有$x \equiv 21b_1+15b_2,b_1 \in \{ 1,4\},b_2 \in \{3,5,6\}$,计算所有组合，(例如，$b_1=1,b_2=3,x=21 \times 1 + 15 \times 3=66 \equiv 31 (mod\ 35)$),可得题中方程全部解为$x\equiv 31,26,6,24,19,34(mod\ 35)$.
\end{solution}
